SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Transposition table</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Transposition table</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>A <b>transposition table</b> is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the value of the position is retrieved from the table, avoiding re-searching the game tree below that position. Transposition tables are primarily useful in <a href="Perfect-information_game" class="mw-redirect" title="Perfect-information game">perfect-information games</a> (where the entire state of the game is known to all players at all times). The usage of transposition tables is essentially <a href="Memoization" title="Memoization">memoization</a> applied to the tree search and is a form of <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>.

</p><p>Transposition tables are typically implemented as <a href="Hash_table" title="Hash table">hash tables</a> encoding the current board position as the hash index. The number of possible positions that may occur in a game tree is an exponential function of depth of search, and can be thousands to millions or even much greater. Transposition tables may therefore consume most of available system memory and are usually most of the <a href="Memory_footprint" title="Memory footprint">memory footprint</a> of game playing programs.

</p>

<div class="mw-heading mw-heading2"><h2 id="Functionality">Functionality</h2></div>

<p>Game-playing programs work by analyzing millions of positions that could arise in the next few moves of the game. Typically, these programs employ strategies resembling <a href="Depth-first_search" title="Depth-first search">depth-first search</a>, which means that they do not keep track of all the positions analyzed so far. In many games, it is possible to reach a given position in more than one way. These are called <a href="Transposition_(chess)" title="Transposition (chess)">transpositions</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> In <a href="Chess" title="Chess">chess</a>, for example, the sequence of moves <i><b>1.</b> d4 Nf6 <b>2.</b> c4 g6</i> (see <a href="Algebraic_chess_notation" class="mw-redirect" title="Algebraic chess notation">algebraic chess notation</a>) has 4 possible transpositions, since either player may swap their move order. In general, after <i>n</i> moves, an upper limit on the possible transpositions is (<i>n</i>!)<sup>2</sup>. Although many of these are illegal move sequences, it is still likely that the program will end up analyzing the same position several times.

</p><p>To avoid this problem, transposition tables are used. Such a table is a <a href="Hash_table" title="Hash table">hash table</a> of each of the positions analyzed so far up to a certain depth. On encountering a new position, the program checks the table to see whether the position has already been analyzed; this can be done quickly, in amortized constant time. If so, the table contains the value that was previously assigned to this position; this value is used directly. If not, the value is computed, and the new position is entered into the hash table.

</p><p>The number of positions searched by a computer often greatly exceeds the memory constraints of the system it runs on; thus not all positions can be stored. When the table fills up, less-used positions are removed to make room for new ones; this makes the transposition table a kind of <a href="Cache_(computing)" title="Cache (computing)">cache</a>.

</p><p>The computation saved by a transposition table lookup is not just the evaluation of a single position. Instead, the evaluation of an entire subtree is avoided. Thus, transposition table entries for nodes at a shallower depth in the game tree are more valuable (since the size of the subtree rooted at such a node is larger) and are therefore given more importance when the table fills up and some entries must be discarded.

</p><p>The hash table implementing the transposition table can have other uses than finding transpositions. In <a href="Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">alpha–beta pruning</a>, the search is fastest (in fact, optimal) when the child of a node corresponding to the best move is always considered first. Of course, there is no way of knowing the best move beforehand, but when <a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">iterative deepening</a> is used, the move that was found to be the best in a shallower search is a good approximation. Therefore this move is tried first. For storing the best child of a node, the entry corresponding to that node in the transposition table is used.

</p><p>Use of a transposition table can lead to incorrect results if the graph-history interaction problem is not studiously avoided. This problem arises in certain games because the history of a position may be important. For example, in <a href="Chess" title="Chess">chess</a> a player may not castle if the king or the rook to be castled with has moved during the course of the game. A common solution to this problem is to add the castling rights as part of the <a href="Zobrist_hashing" title="Zobrist hashing">Zobrist hashing</a> key. Another example is <a href="Threefold_repetition" title="Threefold repetition">draw by repetition</a>: given a position, it may not be possible to determine whether it has already occurred. A solution to the general problem is to store history information in each node of the transposition table, but this is inefficient and rarely done in practice.

</p>

<div class="mw-heading mw-heading2"><h2 id="Replacement_strategies">Replacement strategies</h2></div>

<p>A transposition table is a cache whose maximum size is limited by available system memory, and it may overflow at any time. In fact, it is expected to overflow, and the number of positions cacheable at any time may be only a small fraction (even orders of magnitude smaller) than the number of nodes in the game tree. The vast majority of nodes are not transposition nodes, i.e. positions that will recur, so effective replacement strategies that retain potential transposition nodes and replace other nodes can result in significantly reduced tree size. Replacement is usually based on tree depth and aging: nodes higher in the tree (closer to the root) are favored, because the subtrees below them are larger and result in greater savings; and more recent nodes are favored because older nodes are no longer similar to the current position, so transpositions to them are less likely.

</p><p>Other strategies are to retain nodes in the principal variation, nodes with larger subtrees regardless of depth in the tree, and nodes that caused cutoffs.

</p>

<div class="mw-heading mw-heading2"><h2 id="Size_and_performance">Size and performance</h2></div>

<p>Though the fraction of nodes that will be transpositions is small, the game tree is an exponential structure, so caching a very small number of such nodes can make a significant difference. In chess, search time reductions of 0-50% in complex middle game positions and up to a factor of 5 in the end game have been reported.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Related_techniques">Related techniques</h2></div>

<ul><li>Similar techniques can be used to cache evaluations of certain features of a position. For example, a <i>pawn hash table</i> can be used to store an evaluation of the <a href="Pawn_(chess)" title="Pawn (chess)">pawn</a> structures in a position. Since the number of pawn positions examined is generally much smaller than the total number of positions searched, the pawn hash table has a very high <a href="Cache_(computing)#Operation" title="Cache (computing)">hit rate</a>, allowing a program to spend more time on sophisticated pawn evaluations because they are reused many times.</li>

<li>A <i>refutation table</i> can be used to store sequences of moves from the root node to leaf nodes. This includes the <a href="Principal_variation" class="mw-redirect" title="Principal variation">principal variation</a> and responses to other lines showing that they are inferior. Refutation tables were sometimes used instead of transposition tables in the earlier years of computer chess, when memory was more limited. Some modern chess programs use refutation tables in addition to transposition tables for move ordering, while most do not use them at all.</li>

<li>Static bitmaps of the possible moves of each type of piece on each space of the board can be cached at program initialization, so that the legal moves of a piece (or together, all legal moves for move generation) can be retrieved with a single memory load instead of having to be serially enumerated. These are commonly used in bitboard implementations.</li></ul>

<ul><li><a href="Minimax_algorithm" class="mw-redirect" title="Minimax algorithm">Minimax algorithm</a></li>

<li><a href="Alpha-beta_pruning" class="mw-redirect" title="Alpha-beta pruning">Alpha-beta pruning</a></li>

<li><a href="Zobrist_hashing" title="Zobrist hashing">Zobrist hashing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes_and_references">Notes and references</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-ii-data-structures-r1046">Transposition Tables</a>, Gamedev.net, Francois-Dominic Laramee.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Atkin, L. and Slate, D., 1977, "Chess 4.5, the Northwestern University Chess Program", in Chess Skill in Man and Machine, Peter W. Frey, Ed. Springer-Verlag, New York, NY</span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20070521015918/http://www.sigmachess.com/_usersmanual/ManualData/TransTables.html">Transposition Tables</a> Sigmachess.com</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20070822204120/http://www.seanet.com/~brucemo/topics/hashing.htm">Technical The Main Transposition Table</a> (information on the data structure and implementation)</li>

<li><a rel="nofollow" class="external text" href="http://www.cs.ualberta.ca/~tony/ICCA/anatomy.html">The anatomy of chess programs</a> T.A. Marsland, University of Alberta</li>

<li><a rel="nofollow" class="external text" href="https://www.chessprogramming.org/Transposition_Table">Transposition Table</a> The Chess Programming Wiki</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-23" href="https://en.wikipedia.org/wiki/?title=Transposition_table&oldid=1296968184">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>